<!-- The documentation for conversion of some form of automaton to a RE. -->

<HTML><HEAD>
<TITLE>Convert FA to RE</TITLE>
</HEAD><BODY>

<H1>Convert FA to RE</H1>

<P>The idea behind the transformation is that an FA is repeatedly collapsed until there is a single initial and different single final state, with transitions between them.  This reformed FA is called a <DFN>generalized transition graph</DFN>.</P>

<H2>Steps</H2>

<P>On screen directions walk the user through every step of the transformation.</P>

<P><IMG SRC="images/fsa2re/1.png" ALT="" WIDTH="215" HEIGHT="189" ALIGN="bottom"> In the process of each step, we will pretend to convert this automaton.</P>

<OL>
<LI><P>The FA is transformed so that there is a single final state that is not the initial state.  First, the user creates a new final state.  Then, the user inserts lambda transitions from the old final states to the new final state.  This is accomplished with the regular state creator (<IMG SRC="../ICON/state.gif" ALT="" WIDTH="16" HEIGHT="16">) and transition creator (<IMG SRC="../ICON/transition.gif" ALT="" WIDTH="16" HEIGHT="16">) tools.  The transition creator knows that if we are on this step, we will only be interested in creating lambda transitions.  If there is already only a single final state, this step is skipped.  The example does not require this step.</P></LI>

<LI><P><IMG SRC="images/fsa2re/2.png" WIDTH="215" HEIGHT="186" ALIGN="bottom"> If there are multiple transitions from and to any two given states, they are combined into a single transition.  For example, if from state <VAR>q<SUB>i</SUB></VAR> to <VAR>q<SUB>j</SUB></VAR> there are two transitions <VAR>a</VAR> and <VAR>b</VAR>, they are combined into the regular expression transition <VAR>a+b</VAR>.  The user does this with the "Transition Collapser" tool (<IMG SRC="../ICON/collapse.gif" ALT="" WIDTH="16" HEIGHT="16">).  To collapse multiple transitions between states, click one of these transitions while the tool is active.  If there is no pair of states with multiple transitions between them, this step is skipped.</P></LI>

<LI><P><IMG SRC="images/fsa2re/3.png" WIDTH="218" HEIGHT="190" ALIGN="bottom"> Empty transitions are added between all pairs of states for which there is no transition; that is, if from <VAR>q<SUB>i</SUB></VAR> to <VAR>q<SUB>j</SUB></VAR> there is no transition, an empty transition is added from <VAR>q<SUB>i</SUB></VAR> to <VAR>q<SUB>j</SUB></VAR>.  Note that empty transitions are not lambda transitions!  To add empty transitions for this step, use the transition tool (<IMG SRC="../ICON/transition.gif" ALT="" WIDTH="16" HEIGHT="16">) as you normally do.  Since this step assumes you will only be adding empty transitions, dragging out a transition will automatically create an empty transition.  The example picture shows all the necessary empty transitions needed: note the empty set <IMG SRC="entities/empty.png" WIDTH="11" HEIGHT="11" ALIGN="middle"> symbol.  If there is no pair of states without a transition between them, this step is skipped.</P></LI>

<LI><P><IMG SRC="images/fsa2re/collapse-state.png" WIDTH="288" HEIGHT="157" BORDER="1" ALIGN="bottom"> <IMG SRC="images/fsa2re/4.png" WIDTH="214" HEIGHT="101" ALIGN="bottom"> At this point, all non-initial, non-final states are collapsed, one at a time.  To collapse a state, select the "State Collapser" tool (<IMG SRC="../ICON/state_collapse.gif" WIDTH="16" HEIGHT="16">) tool, and click on the state you wish to collapse.  In the example, the only state to collapse is <VAR>q<SUB>1</SUB></VAR></P>.  When you click on a state with the collapser, a window pops up, as shown above, showing the new transitions for the automaton; as JFLAP will soon remove <VAR>q<SUB>1</SUB></VAR>, certain transitions have to be reformed to ensure that the automaton accepts the same language.  In the example window shown, from state <VAR>q<SUB>0</SUB></VAR> to <VAR>q<SUB>2</SUB></VAR>, there will be a transition <VAR>((a+b)c*)(b+c)</VAR>.  If in this window an expression is selected, in the editor, those transitions that were combined to form the expression will be highlighted.  When this inspection has finished, press "Finalize" and all transitions will be </P></LI>

<LI><P>Once only the final and initial states remain, this generalized transition graph will yield a regular expression.  One can use the "Export" button to put this expression into a regular expression environment.</P></LI>
</OL>

<P>As a final point, the "Do It" button will complete the current step.</P>

</BODY></HTML>
